package _interview100;

/**
 * 34. 在排序数组中查找元素的第一个和最后一个位置
 */
public class No34 {
    private int[] nums;

    public int[] searchRange(int[] nums, int target) {
        this.nums = nums;
        int n = nums.length;
        int start = lowerBound(0, n - 1, target);
        if (start == n || nums[start] != target) return new int[]{-1, -1};

        int end = lowerBound(start, n - 1, target + 1) - 1;
        return new int[]{start, end};
    }

    private int lowerBound(int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return left;
    }
}
